home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / interval_set.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  3.4 KB  |  93 lines
  1.  
  2. {\magonebf  6.4 Sets of intervals (interval\_set)}
  3.  
  4. \decl interval\_set I
  5.  
  6. {\bf 1. Definition}
  7.  
  8. An instance $S$ of the parameterized data type \name\ is a 
  9. collection of items ($is\_item$). Every item in $S$ contains a closed 
  10. interval of the real numbers as key and an information from data type $I$, 
  11. called the information type of $S$. The number of items in $S$ is called 
  12. the size of $S$. An interval set of size zero is said to be empty. We use 
  13. $<x,y,i>$ to denote the item with interval $[x,y]$ and information $i$, 
  14. $x$ ($y$) is called the left (right) boundary of the item. For each 
  15. interval $[x,y] \subset \real$ there is at most one item $<x,y,i> \in S$.
  16.  
  17.  
  18.  
  19. \bigskip
  20. {\bf 2. Creation}
  21.  
  22. \create S {}
  23.  
  24. creates an instance \var\ of type \name\ and initializes \var\ to the 
  25. empty set. 
  26.  
  27.  
  28.  
  29. \bigskip
  30. {\bf 3. Operations}
  31.  
  32. \+\cleartabs & \hskip 2.6truecm & \hskip 5.5truecm &\cr
  33. \+\op double     left {is\_item\ it}  
  34.                             {returns the left boundary of item $it$.}
  35. \+\nop                      {\precond $it$ is an item in \var.}
  36. \smallskip
  37. \+\op double     right {is\_item\ it} 
  38.                                     {returns the right boundary of item $it$.}
  39. \+\nop                              {\precond $it$ is an item in \var.}
  40. \smallskip
  41. \+\op I        inf {is\_item\ it}   
  42.                                     {returns the information of item $it$.}
  43. \+\nop                              {\precond $it$ is an item in \var.}
  44. \smallskip
  45. \+\op is\_item insert {double\ x,\ double\ y,\ I\ i} {}
  46. \+\nop                {associates the information $i$ with interval}
  47. \+\nop                {$[x,y]$. If there is an item $<x,y,j>$ in \var }
  48. \+\nop                {then $j$ is replaced by $i$, else a new item }
  49. \+\nop                {$<x,y,i>$ is added to $S$. In both cases }
  50. \+\nop                {the item is returned.}
  51. \smallskip
  52. \+\op is\_item lookup {double\ x,\ double\ y} 
  53.                       {returns the item with interval $[x,y]$}
  54. \+\nop                {(nil if no such item exists in \var).}
  55. \smallskip
  56. \+\op list\<is\_item\>  intersection {double\ a,\ double\ b}  {}
  57. \+\nop                {returns all items $<x,y,i>\ \in\ S$ with}
  58. \+\nop                {$[x,y] \cap [a,b] \neq \emptyset$.}
  59. \smallskip
  60. \+\op void del {double\ x,\ double\ y}         
  61.                       {deletes the item with interval $[x,y]$}
  62. \+\nop                {from \var.}
  63. \smallskip
  64. \+\op void del\_item {is\_item\ it}   
  65.                               {removes item $it$ from \var.}
  66. \+\nop                        {\precond $it$ is an item in \var.}
  67. \smallskip
  68. \+\op void change\_inf {is\_item\ it,\ I\ i} 
  69.                               {makes $i$ the information of item $it$.}
  70. \+\nop                        {\precond $it$ is an item in \var.}
  71. \smallskip
  72. \+\op void clear {}           
  73.                               {makes \var\ the empty interval\_set.}
  74. \smallskip 
  75. \+\op bool empty {}           
  76.                               {returns true iff \var\ is empty.}
  77. \smallskip 
  78. \+\op int  size {}            
  79.                               {returns the size of \var.}
  80.  
  81.  
  82.  
  83. \bigskip
  84. {\bf 4. Implementation}
  85.  
  86. Interval sets are implemented by two-dimensional range trees [Wi85, Lu78].
  87. Operations insert, lookup, del\_item and del take time $O(\log^2 n)$,
  88. intersection takes time $O(k + \log^2 n)$, where $k$ is the size
  89. of the returned list. Operations left, right, inf, empty, and size
  90. take time $O(1)$, and clear $O(n\log n)$. Here $n$ is always the 
  91. current size of the interval set. The space requirement is $O(n\log n)$.
  92.  
  93.